package partial;

public class Arbori {

    public void traverseaza_preordine_recursiv(NodA x) {
        if (x == null) {
            return;
        }
        /*1*/ System.out.println("Nodul vizitat este " + x.val + "\n");
        /*2*/ if (x.s != null) {
            traverseaza_preordine_recursiv(x.s);
        }
        /*3*/ if (x.d != null) {
            traverseaza_preordine_recursiv(x.d);
        }
    }

    public void traverseaza_inordine_recursiv(NodA x) {
        if (x == null) {
            return;
        }
        /*2*/ if (x.s != null) {
            traverseaza_inordine_recursiv(x.s);
        }
        /*1*/ System.out.println("Nodul vizitat este " + x.val + "\n");
        /*3*/ if (x.d != null) {
            traverseaza_inordine_recursiv(x.d);
        }
    }

    public void traverseaza_postordine_recursiv(NodA x) {
        if (x == null) {
            return;
        }
        /*2*/ if (x.s != null) {
            traverseaza_postordine_recursiv(x.s);
        }
        /*3*/ if (x.d != null) {
            traverseaza_postordine_recursiv(x.d);
        }
        /*1*/ System.out.println("Nodul vizitat este " + x.val + "\n");
    }

    public void traverseaza_preordine_iterativ_1(NodA x) {
        StivaA stv = new StivaA();
        stv.push(x);
        System.out.println("********Traversarea iterativa in preordine_1 ***********\n");
        while (!stv.isEmpty()) {
            NodA xt = stv.pop();
            System.out.println("Nodul vizitat este " + xt.val + "\n");
            if (xt.d != null) {
                stv.push(xt.d);
            }
            if (xt.s != null) {
                stv.push(xt.s);
            }
        }
    }

    public void traverseaza_preordine_iterativ_2(NodA x) {
        StivaAX stv = new StivaAX();
        stv.push(new NodX(x, 0));
        System.out.println("********Traversarea iterativa in preordine_2 ***********\n");
        while (!stv.isEmpty()) {
            NodX xt = (NodX) stv.pop();
            if (xt.x.s == null && xt.x.d == null) {
                System.out.println("Nodul vizitat este " + xt.x.val + "\n");
            } else if (xt.z == 1) {
                System.out.println("Nodul vizitat este " + xt.x.val + "\n");
            } else {
                /*1*/ if (xt.x.d != null) {
                    stv.push(new NodX(xt.x.d, 0));
                }
                /*2*/ if (xt.x.s != null) {
                    stv.push(new NodX(xt.x.s, 0));
                }
                /*3*/ stv.push(new NodX(xt.x, 1));
            }
        }
    }

    public void traverseaza_inordine_iterativ_2(NodA x) {
        StivaAX stv = new StivaAX();
        stv.push(new NodX(x, 0));
        System.out.println("********Traversarea iterativa in inordine ***********\n");
        while (!stv.isEmpty()) {
            NodX xt = (NodX) stv.pop();
            if (xt.x.s == null && xt.x.d == null) {
                System.out.println("Nodul vizitat este " + xt.x.val + "\n");
            } else if (xt.z == 1) {
                System.out.println("Nodul vizitat este " + xt.x.val + "\n");
            } else {
                /*1*/ if (xt.x.d != null) {
                    stv.push(new NodX(xt.x.d, 0));
                }
                /*3*/ stv.push(new NodX(xt.x, 1));
                /*2*/ if (xt.x.s != null) {
                    stv.push(new NodX(xt.x.s, 0));
                }
            }
        }
    }

    public void traverseaza_postordine_iterativ_2(NodA x) {
        StivaAX stv = new StivaAX();
        stv.push(new NodX(x, 0));
        System.out.println("********Traversarea iterativa in postordine ***********\n");
        while (!stv.isEmpty()) {
            NodX xt = (NodX) stv.pop();
            if (xt.x.s == null && xt.x.d == null) {
                System.out.println("Nodul vizitat este " + xt.x.val + "\n");
            } else if (xt.z == 1) {
                System.out.println("Nodul vizitat este " + xt.x.val + "\n");
            } else {
                /*3*/ stv.push(new NodX(xt.x, 1));
                /*1*/ if (xt.x.d != null) {
                    stv.push(new NodX(xt.x.d, 0));
                }
                /*2*/ if (xt.x.s != null) {
                    stv.push(new NodX(xt.x.s, 0));
                }
            }
        }
    }

    public void traverseaza_latime(NodA x) {
        CoadaA q = new CoadaA();
        q.put(x);
        System.out.println("********Traversarea in latime ***********\n");
        while (!q.isEmpty()) {
            NodA xt = q.get();
            System.out.println("Nod viz= " + xt.val);
            if (xt.s != null) {
                q.put(xt.s);
            }
            if (xt.d != null) {
                q.put(xt.d);
            }
        }
    }

    public void insert_node(NodA x, int val) {
        System.out.println("---sunt in " + x.val);
        if (val == x.val) {
            System.out.println("!nodul cu val " + val + " exista deja");
        } else if (val < x.val) {
            System.out.println(val + " < " + x.val);
            if (x.s == null) {
                x.s = new NodA(val);
                System.out.println("adaugat " + val + " la stg lui " + x.val);
            } else {
                insert_node(x.s, val);
            }
        } else {
            System.out.println(val + " > " + x.val);
            if (x.d == null) {
                x.d = new NodA(val);
                System.out.println("adaugat " + val + " la drp lui " + x.val);
            } else {
                insert_node(x.d, val);
            }
        }
    }

    public int sumaNivel(NodA x, int niv) {
        CoadaA arbore = new CoadaA();
        CoadaL nivs = new CoadaL();
        arbore.put(x);
        nivs.put(0);
        int suma = 0;
        while (!arbore.isEmpty()) {
            NodA temp = arbore.get();
            int nivCurent = nivs.get();
            if (nivCurent == niv) {
                suma += temp.val;
            } else {
                if (temp.s != null) {
                    arbore.put(temp.s);
                    nivs.put(nivCurent + 1);
                }
                if (temp.d != null) {
                    arbore.put(temp.d);
                    nivs.put(nivCurent + 1);
                }
            }
        }
        return suma;
    }

    public int inaltime(NodA x) {
        if (x == null) {
            return -1;
        }

        int stgx = inaltime(x.s);
        int drx = inaltime(x.d);

        if (stgx > drx) {
            return stgx + 1;
        } else {
            return drx + 1;
        }
    }

    public void stergeFrunze(NodA x) {
        if (x.s != null) {
            if (isFrunza(x.s)) {
                x.s = null;
            } else {
                stergeFrunze(x.s);
            }
        }
        if (x.d != null) {
            if (isFrunza(x.d)) {
                x.d = null;
            } else {
                stergeFrunze(x.d);
            }
        }
    }

    public boolean isFrunza(NodA x) {
        if (x.s == null && x.d == null) {
            return true;
        } else {
            return false;
        }
    }

    public NodA search(NodA x, int val) {
        CoadaA q = new CoadaA();
        NodA res = null;
        q.put(x);
        //System.out.println("********Traversarea in latime ***********\n");
        while (!q.isEmpty()) {
            NodA xt = q.get();
            if (xt.val == val) {
                res = xt;
                break;
            }
            // System.out.println("Nod viz= " + xt.val);
            if (xt.s != null) {
                q.put(xt.s);
            }
            if (xt.d != null) {
                q.put(xt.d);
            }
        }
        return res;
    }

    public NodA cautareNod(NodA x, int val){
        if (x.val == val) {
            System.out.println("Am gasit nodul cu valoarea = " + x.val);
            return x;
        }
        if (x.s != null) {
            cautareNod(x.s, val);
        }
        if (x.d != null) {
            cautareNod(x.d, val);
        }
        return null;

    }
    
    public static void main(String[] args) {
        Arbori a = new Arbori();
        NodA r = new NodA(42);
        r.s = new NodA(17);
        r.d = new NodA(65);
        r.s.s = new NodA(9);
        r.s.d = new NodA(23);
        r.s.s.s = new NodA(3);
        r.s.s.d = new NodA(10);
        r.s.d.s = new NodA(18);
        r.s.d.d = new NodA(25);
        r.d.s = new NodA(50);
        r.d.d = new NodA(70);
        r.d.s.s = new NodA(49);
        r.d.s.d = new NodA(55);
        r.d.d.s = new NodA(69);
        r.d.d.d = new NodA(71);

//        NodA r = new NodA(1);
//        r.s = new NodA(2);
//        r.d = new NodA(6);
//        r.s.s = new NodA(3);
//        r.s.s.s = new NodA(4);
//        r.s.s.d = new NodA(5);
//        r.d.s = new NodA(7);
//        r.d.s.d = new NodA(8);


        //a.traverseaza_preordine_recursiv(r);
        //a.traverseaza_inordine_recursiv(r);

        //a.traverseaza_postordine_recursiv(r);
        //a.traverseaza_preordine_iterativ_1(r);
        //a.traverseaza_preordine_iterativ_2(r);  	
        //a.traverseaza_inordine_iterativ_2(r);  	
        //a.traverseaza_postordine_iterativ_2(r);  	

        a.traverseaza_latime(r);
        System.out.println(a.search(r, 23).val);
        //System.out.println(a.sumaNivel(r, 9));
    }
}
